排序大组合-选择、插入、希尔、Shuffling、归并、快速

选择排序（SelectionSort）

1.在第i次迭代的时候，找i+1~N中的最小值对应下标min 2.swap a[i]和a[min]（一定要自己写一遍加深印象！）

    import java.util.Random;
    public class selectionSort{
    	public static void sort(Comparable[] a){
    	 int len=a.length;
    	 for(int i=0;i<len;i++){
    	     int min=i;
    	     for(int j=i+1;j<len;j++){
    	         if (less(a[j],a[min]))
    	         min=j;}///非常需要注意，内部循环是不换值的，只找最小值
    	     exch(a,i,min);
    	     
    	 }   
    	}
    
    	private static boolean less(Comparable a,Comparable b){
    		return a.compareTo(b)<0;
    	}
    	private static void exch(Comparable[] a,int i, int j){
    		Comparable temp;
    		temp=a[i];
    		a[i]=a[j];
    		a[j]=temp;
    	}
   		//测试验证
    	public static void main(String[] args){
    		Comparable test[] =new Comparable[10];		
    		for (int i=0;i<10 ; i++) {
    			test[i]=new java.util.Random().nextInt(15);
    		}
    		// Comparable test[]={'f','s','d','g'};
    		int N=test.length;
    		for (int i=0;i<N;i++){
    			System.out.println(test[i]);
    		}
    		selectionSort.sort(test); 
    		System.out.println();
    		for (int i=0;i<N;i++){
    			System.out.println(test[i]);
    		}
    	}
    }

运行结果：（随机的，大家都不一样） 6 13 6 11 10 10 13 4 7 5 4 5 6 6 7 10 10 11 13 13
分析：算法复杂度O（N*N）

即使输入是已经排序，花费仍是Quadratic Time（二次的） 非常暴力原始的方法。

插入排序（insertionSort）

每次迭代[i]，把a[i]和它位于它左边的较大值互换。

    public class Insertionsort{
    	public static void sort(Comparable[] a){
    		int N=a.length;
    		for(int i=0;i<N;i++)		
    			for(int j=i;j>0;j--)//j始于i
    				if (less(a[j],a[j-1]))
    					exch(a,j,j-1); //内圈换值
    				else 
    					break;
    	}
    
    	private static boolean less(Comparable a,Comparable b){
    			return a.compareTo(b)<0;
    	}
    
    	private static void exch(Comparable[] a,int i, int j){
    		Comparable temp;
    		temp=a[i];
    		a[i]=a[j];
    		a[j]=temp;
    	}
    	//测试验证
    	public static void main(String[] args){
    		Comparable test[] =new Comparable[10];		
    		for (int i=0;i<10 ; i++) {
    			test[i]=new java.util.Random().nextInt(15);//0~14随机数
    		}
    		// Comparable test[]={'f','s','d','g'};
    		int N=test.length;
    		for (int i=0;i<N;i++){
    			System.out.print(test[i]+" ");
    		}
    		Insertionsort.sort(test); 
    		System.out.println();
    		for (int i=0;i<N;i++){
    			System.out.print(test[i]+" ");
    		}
    	}
    }

运行结果： 11 3 10 6 12 0 11 9 3 12 0 3 3 6 9 10 11 11 12 12 [Finished in 0.8s] 复杂度： stability：stable，左移位置不多，不会跨越较多元素。

希尔排序（Shell 排序）

总体思想是，跳跃式的一组一组排，按h=3h+1，比如h=4时，先排a[0],a[4],a[8]....再排a[1],a[5]...再对每组按h=1排，就排好了

    public static void sort(Comparable[] a)
       {
          int N = a.length;
          int h = 1;
          while (h < N/3) h = 3*h + 1; // 1, 4, 13, 40, 121, 364, ...
          while (h >= 1)
          {  // h-sort the array.
             for (int i = h; i < N; i++)
             {
                for (int j = i; j >= h && less(a[j], a[j-h]); j -= h)
                   exch(a, j, j-h);
             }
             
             h = h/3;
             }
    }